home *** CD-ROM | disk | FTP | other *** search
/ C++ für Kids / C++ for kids.iso / SETUP / US / CBUILDER / DATA.Z / MAP.H < prev    next >
C/C++ Source or Header  |  1997-02-13  |  17KB  |  487 lines
  1. #ifndef __STD_MAP__
  2. #define __STD_MAP__
  3. /* $Revision:   8.1  $ */
  4.  
  5. /***************************************************************************
  6.  *
  7.  * map - declarations for the Standard Library map class
  8.  *
  9.  * $Id: map,v 1.31 1995/08/23 23:54:42 lijewski Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED
  29.  *
  30.  * The software and information contained herein are proprietary to, and
  31.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  32.  * intends to preserve as trade secrets such software and information.
  33.  * This software is furnished pursuant to a written license agreement and
  34.  * may be used, copied, transmitted, and stored only in accordance with
  35.  * the terms of such license and with the inclusion of the above copyright
  36.  * notice.  This software and information or any other copies thereof may
  37.  * not be provided or otherwise made available to any other person.
  38.  *
  39.  * Notwithstanding any other lease or license that may pertain to, or
  40.  * accompany the delivery of, this computer software and information, the
  41.  * rights of the Government regarding its use, reproduction and disclosure
  42.  * are as set forth in Section 52.227-19 of the FARS Computer
  43.  * Software-Restricted Rights clause.
  44.  *
  45.  * Use, duplication, or disclosure by the Government is subject to
  46.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  47.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  48.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  49.  * P.O. Box 2328, Corvallis, Oregon 97339.
  50.  *
  51.  * This computer software and information is distributed with "restricted
  52.  * rights."  Use, duplication or disclosure is subject to restrictions as
  53.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  54.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  55.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  56.  * then the "Alternate III" clause applies.
  57.  *
  58.  **************************************************************************/
  59.  
  60. #include <stdcomp.h>
  61.  
  62. #ifndef Allocator
  63. #define Allocator allocator
  64. #include <memory>
  65. #endif
  66.  
  67. #ifdef __BORLANDC__
  68. #pragma warn -inl
  69. #endif
  70.  
  71. #include <tree>
  72.  
  73. #ifndef RWSTD_NO_NAMESPACE
  74. namespace std {
  75. #endif
  76.  
  77. //
  78. // This is used in the implementation of map and multimap.
  79. //
  80.  
  81. template <class T, class U>
  82. struct select1st : public unary_function<T, U>
  83. {
  84.     const U& operator() (const T& x) const { return x.first; }
  85. };
  86.  
  87. //
  88. // First the map stuff.
  89. //
  90.  
  91. #ifndef RWSTD_NO_DEFAULT_TEMPLATES
  92. template<class Key, class T, class Compare = less<Key> >
  93. #else
  94. template<class Key, class T, class Compare>
  95. #endif /* RWSTD_NO_DEFAULT_TEMPLATES */
  96. class map
  97. {
  98.   public:
  99.     //
  100.     // types
  101.     //
  102.     typedef Key                key_type;
  103. #ifndef RWSTD_NO_CONST_INST
  104.     typedef pair<const Key, T> value_type;
  105. #else
  106.     typedef pair<Key, T>       value_type;
  107. #endif
  108.     typedef Compare            key_compare;
  109.  
  110.     class value_compare : public binary_function<value_type, value_type, bool>
  111.     {
  112.         friend class map<Key, T, Compare>;
  113.       protected:
  114.         Compare comp;
  115.         value_compare (Compare c) : comp(c) {}
  116.       public:
  117.         bool operator() (const value_type& x, const value_type& y) const
  118.         {
  119.             return comp(x.first, y.first);
  120.         }
  121.     };
  122.  
  123.   private:
  124.  
  125.     typedef rb_tree<key_type, value_type,
  126.                     select1st<value_type, key_type>, key_compare> rep_type;
  127.     rep_type t;
  128.  
  129.   public:
  130.     //
  131.     // types
  132.     //
  133.     typedef typename rep_type::reference                reference;
  134.     typedef typename rep_type::const_reference          const_reference;
  135.     typedef typename rep_type::iterator                 iterator;
  136.     typedef typename rep_type::const_iterator           const_iterator;
  137.     typedef typename rep_type::size_type                size_type;
  138.     typedef typename rep_type::difference_type          difference_type;
  139.     typedef typename rep_type::reverse_iterator         reverse_iterator;
  140.     typedef typename rep_type::const_reverse_iterator   const_reverse_iterator;
  141.     //
  142.     // construct/copy/destroy
  143.     //
  144.     explicit map (const Compare& comp = Compare()) : t(comp, false) {}
  145.  
  146. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  147.     template<class InputIterator>
  148.     map (InputIterator first, InputIterator last,
  149.          const Compare& comp = Compare()) : t(first, last, comp, false) {}
  150. #else
  151.     map (const value_type* first, const value_type* last,
  152.          const Compare& comp = Compare()) : t(first, last, comp, false) {}
  153.     map (iterator first, iterator last,
  154.          const Compare& comp = Compare()) : t(first, last, comp, false) {}
  155.     map (const_iterator first, const_iterator last,
  156.          const Compare& comp = Compare()) : t(first, last, comp, false) {}
  157. #endif
  158.  
  159.     map (const map<Key, T, Compare>& x) : t(x.t, false) {}
  160.     map<Key, T, Compare>& operator= (const map<Key, T, Compare>& x)
  161.     {
  162.           t = x.t; return *this;
  163.     }
  164.     //
  165.     // iterators
  166.     //
  167.  
  168.     iterator               begin  ()       { return t.begin();  }
  169.     const_iterator         begin  () const { return t.begin();  }
  170.     iterator               end    ()       { return t.end();    }
  171.     const_iterator         end    () const { return t.end();    }
  172.     reverse_iterator       rbegin ()       { return t.rbegin(); }
  173.     const_reverse_iterator rbegin () const { return t.rbegin(); }
  174.     reverse_iterator       rend   ()       { return t.rend();   }
  175.     const_reverse_iterator rend   () const { return t.rend();   }
  176.     //
  177.     // capacity
  178.     //
  179.     bool      empty    () const { return t.empty();    }
  180.     size_type size     () const { return t.size();     }
  181.     size_type max_size () const { return t.max_size(); }
  182.     //
  183.     // element access
  184.     //
  185.     T& operator[] (const key_type& k)
  186.     {
  187.         value_type tmp(k,T()); return (*((insert(tmp)).first)).second;
  188.     }
  189.     //
  190.     // TODO - fix this once required functionality is specified by WP!!!
  191.     //
  192.     //const T& operator[] (const key_type& k) const
  193.     //{
  194.     //    value_type tmp(k,T()); return (*((insert(tmp)).first)).second;
  195.     //}
  196.     //
  197.     // modifiers
  198.     //
  199. #ifndef RWSTD_NO_RET_TEMPLATE
  200.     pair<iterator,bool> insert (const value_type& x) { return t.insert(x); }
  201. #else
  202.     typedef pair<iterator, bool> pair_iterator_bool;
  203.     //
  204.     // typedef done to get around compiler bug
  205.     //
  206.     pair_iterator_bool insert (const value_type& x) { return t.insert(x); }
  207. #endif
  208.     iterator insert (iterator position, const value_type& x)
  209.     {
  210.         return t.insert(position, x);
  211.     }
  212.  
  213. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  214.     template<class InputIterator>
  215.     void insert (InputIterator first, InputIterator last)
  216.     {
  217.         t.insert(first, last);
  218.     }
  219. #else
  220.     void insert (const value_type* first, const value_type* last)
  221.     {
  222.         t.insert(first, last);
  223.     }
  224.     void insert (iterator first, iterator last)
  225.     {
  226.         t.insert(first, last);
  227.     }
  228.     void insert (const_iterator first, const_iterator last)
  229.     {
  230.         t.insert(first, last);
  231.     }
  232. #endif
  233.  
  234.     void      erase (iterator position)             { t.erase(position);    }
  235.     size_type erase (const key_type& x)             { return t.erase(x);    }
  236.     void      erase (iterator first, iterator last) { t.erase(first, last); }